package 剑指offer;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author: tyy 剑指 Offer
 * 3268. 丢失的数字
    给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
    示例 1：
    输入：nums = [3,0,1]
    输出：2
    解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
 * @create: 2021-10-31 17:40
 * @description:
 **/
// 1、最简单的方法应该是求和，然后和1到n项的数列和对比，相差的数就是缺的这个数
// 2、异或操作（^）是一种很好的方式，不用考虑sum越界问题。
public class Solution18 {
    public int missingNumber(int[] nums) {
        //解法一 排序
        // Arrays.sort(nums);
        // for(int i = 0; i < nums.length; i++){
        //     if(nums[i] != i) return i;
        // }
        // return nums.length;

        //解法二 哈希表
        // Set<Integer> set = new HashSet<>();
        // for(int i = 0; i < nums.length; i++) set.add(nums[i]);
        // for(int i = 0; i <= nums.length; i++)
        //     if(!set.contains(i)) return i;
        // return -1;

        //解法三 位运算
        // int res = nums.length;
        // for(int i = 0; i < nums.length; i++){
        //     res ^= nums[i] ^ i;
        // }
        // return res;

        //解法四 数学
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i]; // 数组元素之和
        }
        return nums.length * (nums.length + 1) / 2 - sum;  // 高斯定律求和-sum就是没有出现在数组中的那个算
    }

    /**直接求和0ms
     * @param nums
     * @return
     */
    public int missingNumber3(int[] nums) {
        int n = nums.length;
        int sum = (n+1)*(n) / 2; // 求和
        for (int i = 0; i < n; i ++)
            sum -= nums[i]; // 逐步相减
        return sum;
    }
    public int missingNumber2(int[] nums) {
        int res = nums.length;
        for (int i = 0; i < nums.length; ++i){
            res ^= nums[i];
            res ^= i;
        }
        return res;
    }
    public int missingNumber1(int[] nums) {
        List list = new ArrayList();
        for (int i = 0; i < nums.length; i++) {
            list.add(nums[i]);
        }
        Collections.sort(list);
        for (int i = 0; i < nums.length+1; i++) {
            boolean contains = list.contains(i);
            if (!contains) {
                return i;
            }
        }

        return 0;
    }
    public static void main(String[] args) {
        int num[] = {3,0,1};
        int number = new Solution18().missingNumber(num);
        System.out.println("number = " + number);
        int i = 3 ^ 0 ^ 1;
        System.out.println("number = " + i);
        System.out.println("number = " + (0^3));  //3
        System.out.println("number = " + (3 ^ 0)); //3
        System.out.println("number = " + (2 ^ 1));// 3
        System.out.println("number = " + (3 ^ 1)); //2

                

    }
}